package array.sliding_window;

import java.util.Arrays;

/*
* 和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。
现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。
数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

示例 1：
输入：nums = [1,3,2,2,5,2,3,7]
输出：5
解释：最长的和谐子序列是 [3,2,2,2,3]
*
示例 2：
输入：nums = [1,2,3,4]
输出：2
*
示例 3：
输入：nums = [1,1,1,1]
输出：0
* */
public class lc594 {
    public static void main(String[] args) {
        int[] nums=new int[]{1,3,2,2,5,2,3,7};
        System.out.println(findLHS(nums));

    }
    public static int findLHS(int[] nums) {
        //先排序再用滑动窗口
        if(nums.length==1) return 0;
        if(nums.length==2){
            if(nums[0]-nums[1]==1||nums[1]-nums[0]==1) return 2;
            return 0;
        }
        int count=0;
        for (int i = 0; i < nums.length-1 ; i++) {
            if(nums[i]==nums[i+1]){
                count++;
            }else {
                break;
            }
        }
        if(count== nums.length-1) return 0;
        Arrays.sort(nums);
        int slow=0;
        int fast=1;
        int bestresult=1;
        int curresult=1;
        while(fast<nums.length){
            curresult=fast-slow+1;
            while(!isHS(nums,slow,fast)){
                slow++;
                if(slow==fast){
                    fast=fast+2;
                }
                curresult=fast-slow+1;
            }
            if(curresult>bestresult){
                bestresult=curresult;
            }
            fast++;
        }
        return bestresult;
    }
    public static boolean isHS(int[] nums,int slow,int fast){//判断是否为和谐子序列
        if(fast-slow==0) return false;
          int min=nums[slow];
          int max=nums[slow];
        for (int i = slow; i <=fast ; i++) {
            if(min>nums[i]) min=nums[i];
            if(max<nums[i]) max=nums[i];
        }
        if(min==max-1){
            return true;
        }
        return false;
    }
}
